package search.bfs;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @Classname : RemoveInvalidParentheses
 * @Description : 301. 删除无效的括号
 * https://leetcode.cn/problems/remove-invalid-parentheses/
 * @Author : cty
 * @Date 2023/5/3 23:27
 */


public class RemoveInvalidParentheses {
    // 广度优先搜索
    public List<String> removeInvalidParentheses(String s) {
        List<String> ans = new ArrayList<>();
        Set<String> curSet = new HashSet<>();
        curSet.add(s);

        while (true) {
            // 若上轮结果中存在有效字符串，即截至上轮已删除最小数量的无效括号，则结束
            for (String cur : curSet) {
                if (isValid(cur)) ans.add(cur);
            }
            if (ans.size() > 0) break;
            // 每轮删除一个括号
            Set<String> nextSet = new HashSet<>();
            for (String str : curSet) {
                for (int i = 0; i < str.length(); i++) {
                    if (str.charAt(i) == '(' || str.charAt(i) == ')') {
                        nextSet.add(str.substring(0, i) + str.substring(i + 1));
                    }
                }
            }
            curSet = nextSet;
        }
        return ans;
    }

    // 判断字符串是否有效
    private boolean isValid(String s) {
        int count = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') count++;
            else if (c == ')') {
                count--;
                if (count < 0) return false;
            }
        }
        return count == 0;
    }
}
